package club.xiaojiawei.back;

import java.util.*;

/**
 * @author 肖嘉威
 * @version 1.0
 * @date 5/22/22 3:42 PM
 * @question 47. 全排列 II
 * @description 给定一个可包含重复数字的序列 nums ，按任意顺序 返回所有不重复的全排列。
 */
public class PermuteUnique47 {

    public static void main(String[] args) {
        PermuteUnique47 test = new PermuteUnique47();
        System.out.println(test.permuteUnique(new int[]{1, 2, 2, 3}));
    }

    /**
     * HashSet去重+递归
     * @param nums
     * @return
     */
    public List<List<Integer>> permuteUnique(int[] nums) {
        for (int num : nums) {
            temp.add(num);
        }
        this.length = nums.length;
        recursion(0);
        return new ArrayList<>(result);
    }

    int length = 0;

    Set<List<Integer>> result = new HashSet<>();

    List<Integer> temp = new ArrayList<>();

    public void recursion(int index){
        if (index == length){
            result.add(new ArrayList<>(temp));
            return;
        }
        for (int i = index; i < length; i++){
            Collections.swap(temp, index, i);
            recursion(index + 1);
            Collections.swap(temp, index, i);
        }
    }

    boolean[] vis;

    /**
     * 官方-搜索回溯
     * @param nums
     * @return
     */
    public List<List<Integer>> permuteUnique2(int[] nums) {
        List<List<Integer>> ans = new ArrayList<List<Integer>>();
        List<Integer> perm = new ArrayList<Integer>();
        vis = new boolean[nums.length];
        Arrays.sort(nums);
        backtrack(nums, ans, 0, perm);
        return ans;
    }

    public void backtrack(int[] nums, List<List<Integer>> ans, int idx, List<Integer> perm) {
        if (idx == nums.length) {
            ans.add(new ArrayList<Integer>(perm));
            return;
        }
        for (int i = 0; i < nums.length; ++i) {
            if (vis[i] || (i > 0 && nums[i] == nums[i - 1] && !vis[i - 1])) {
                continue;
            }
            perm.add(nums[i]);
            vis[i] = true;
            backtrack(nums, ans, idx + 1, perm);
            vis[i] = false;
            perm.remove(idx);
        }
    }

    /**
     * 递归+打标记+排序
     * @param nums
     * @return
     */
    public List<List<Integer>> permuteUnique3(int[] nums) {
        this.length = nums.length;
        Arrays.sort(nums);
        flag = new boolean[this.length];
        recursion(nums);
        return ans;
    }

    List<List<Integer>> ans = new ArrayList<>();
    boolean[] flag = null;

    public void recursion(int[] nums){
        for (int i = 0; i < length; i++){
            if (flag[i] || i > 0 && nums[i] == nums[i - 1] && !flag[i - 1]){
                continue;
            }
            flag[i] = true;
            temp.add(nums[i]);
            if (temp.size() == length){
                ans.add(new ArrayList<>(temp));
            }else {
                recursion(nums);
            }
            flag[i] = false;
            temp.remove(temp.size() - 1);
        }
    }

}
